import java.util.ArrayDeque;
import java.util.LinkedList;
import java.util.Queue;

public class Code {

    private int[][] map = new int[16][16];
    private int[] step = new int[16];
    private int[] pathNum = new int[16];

    public Code() {
        map[0][4] = map[0][1] = 1;
        map[1][5] = map[1][0] = map[1][2] = 1;
        map[2][6] = map[2][1] = map[2][3] = 1;
        map[3][7] = map[3][2] = 1;
        map[4][0] = map[4][5] = 1;
        map[5][1] = map[5][4] = map[5][6] = map[5][9] = 1;
        map[6][2] = map[6][5] = map[6][7] = map[6][10] = 1;
        map[7][3] = map[7][6] = 1;
        map[8][12] = map[8][9] = 1;
        map[9][5] = map[9][8] = map[9][10] = map[9][13] = 1;
        map[10][6] = map[10][9] = map[10][11] = map[10][14] = 1;
        map[11][15] = map[11][10] = 1;
        map[12][8] = map[12][13] = 1;
        map[13][9] = map[13][14] = map[13][12] = 1;
        map[14][10] = map[14][15] = map[14][13] = 1;
        map[15][11] = map[15][14] = 1;
        pathNum[0] = 1;
        build();
    }

    private void build() {
        Queue<Integer> integers = new LinkedList<>();
        integers.add(0);
        while (!integers.isEmpty()) {
            int i = integers.poll();
            for (int j = 0; j < map.length; j++) {
                if (map[i][j] == 1) {//i可以到j
                    if (step[j] == 0 || step[i] + 1 < step[j]) {
                        if(step[j] == 0){//第一次到达
                            integers.add(j);
                        }
                        step[j] = step[i] + 1;
                        pathNum[j] = pathNum[i];
                    } else if (step[j] == step[i] + 1) {
                        pathNum[j] = pathNum[i] + pathNum[j];
                    }
                }
            }
        }
    }

    public void print(int i){
        System.out.println("路径数量:"+pathNum[i]+",长度:"+step[i]);
    }

    public static void main(String[] args) {
        new Code().print(15);
    }


}




















